/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/intersection-of-two-linked-lists
   @Language: C++
   @Datetime: 19-11-21 14:33
   */

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

// Method 1
class Solution {
public:
	ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
		int la=0, lb=0;
		for(ListNode *p=headA; p; ++la, p=p->next);
		for(ListNode *p=headB; p; ++lb, p=p->next);
		if(la<lb) swap(headA, headB);
		for(la=abs(la-lb); la--; headA=headA->next);
		for(; headA!=headB; headA=headA->next, headB=headB->next);
		return headA;
	}
};

// Method 2
class Solution {
public:
	ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
		for(ListNode *a=headA, *b=headB; headA!=headB;){
			headA=headA?headA->next:b;
			headB=headB?headB->next:a;
		}
		return headA==headB?headA:NULL;
	}
};
